package com.lht.leetcodeDemo;

import org.junit.Test;

/**
 * @author Eric
 * @version 1.0
 * @date 2019-05-23
 */
public class SearchInsertPosition {

    @Test
    public void testSearchInsert() {
        SearchInsertPosition position = new SearchInsertPosition();

        int[] nums = new int[]{1, 3};
        System.out.println(position.searchInsert(nums, 2));

    }

    public int searchInsert(int[] nums, int target) {
        /*
            二分查找
                跳出条件
                1.找到了
                2. 确认没找到
                    end-start<=1
                    =0 肯定没找到了
                    =1 情况，可能 num[start] nums[end] =target
         */
        int start = 0;
        int end = nums.length - 1;
        //单独剔除 target一定不在数组内的情况
        if (target < nums[start]) {
            return 0;
        }
        if (target > nums[end]) {
            return end + 1;
        }
        int middle = (start + end) / 2;
        while (end - start > 1) {
            if (nums[middle] > target) {
                end = middle;
            } else if (nums[middle] < target) {
                start = middle;
            } else {
                return middle;
            }
            middle = (end + start) / 2;
        }
        //循环结束，最后一次，有可能考虑漏掉  start end 位 也可以 ==target
        if (nums[start] == target) {
            return start;
        }
        if (nums[end] == target) {
            return end;
        }
        //前后都不等 ，中间也不等，肯定在middle 前或者后了
        return nums[middle] > target ? middle - 1 : middle + 1;
    }

}
